package com.leetcode.algorithm.y19.m02;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

/**
 * leetcode-cn.com
 * (done)556. 下一个更大元素 III
 * (done)150. 逆波兰表达式求值
 * (done)921. 使括号有效的最少添加
 * (done)946. 验证栈序列
 * (done)856. 括号的分数
 * @author: jie.deng
 * @time: 2019年2月20日 上午11:49:13
 */
public class MySolution0220 {
	/**
	 * 556. 下一个更大元素 III
	 * 
     * 给定一个32位正整数 n，你需要找到最小的32位整数，其与 n 中存在的位数完全相同，并且其值大于n。如果不存在这样的32位整数，则返回-1。
     * 
     * 示例 1:
     * 
     * 输入: 12
     * 输出: 21
     * 示例 2:
     * 
     * 输入: 21
     * 输出: -1
	 * @param n
	 * @return
	 */
	public int nextGreaterElement(int n) {
		int src = n;
		List<Integer> list = new ArrayList<Integer>();
		while (src > 0) {
			int i = src % 10;
			list.add(i);
			Collections.sort(list);// 排序
			src = src / 10;

			int max = list.get(list.size() - 1);
			int idxIgnore = list.size() - 1;
			if (max > i) {
				while (list.get(idxIgnore) > i) {
					idxIgnore--;
				}
				idxIgnore = idxIgnore + 1;
				int ret = src * 10 + list.get(idxIgnore);
				for (int idx = 0; idx < list.size(); idx++) {
					if (idx != idxIgnore) {
						if (ret > Integer.MAX_VALUE / 10
								|| (ret == Integer.MAX_VALUE / 10 && list.get(idx) > Integer.MAX_VALUE % 10)) {
							// 考虑溢出
							return -1;
						}
						ret = ret * 10 + list.get(idx);
					}
				}
				return ret;
			}
		}
		return -1;
	}
	
    /**
     * 150. 逆波兰表达式求值
     * 
     * 根据逆波兰表示法，求表达式的值。
     * 
     * 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
     * 
     * 说明：
     * 
     * 整数除法只保留整数部分。
     * 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
     * 示例 1：
     * 
     * 输入: ["2", "1", "+", "3", "*"]
     * 输出: 9
     * 解释: ((2 + 1) * 3) = 9
     * 示例 2：
     * 
     * 输入: ["4", "13", "5", "/", "+"]
     * 输出: 6
     * 解释: (4 + (13 / 5)) = 6
     * 示例 3：
     * 
     * 输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
     * 输出: 22
     * 解释: 
     *   ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
     * = ((10 * (6 / (12 * -11))) + 17) + 5
     * = ((10 * (6 / -132)) + 17) + 5
     * = ((10 * 0) + 17) + 5
     * = (0 + 17) + 5
     * = 17 + 5
     * = 22
     * @param tokens
     * @return
     */
	public int evalRPN(String[] tokens) {
		// 1)如果是数字，先将其转换为整数再入栈
		// 2)如果是运算符，将两个操作数出栈，计算结果再入栈
		// 3)重复1）和2）直到后缀表达式结束，最终栈内的元素即为计算的结果。
		int ret = 0;
		Stack<Integer> stack = new Stack<Integer>();
		for (String str : tokens) {
			if ("+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str)) {
				if (stack.size() >= 2) {
					int i1 = stack.pop();
					int i2 = stack.pop();
					if ("+".equals(str)) {
						ret = i2 + i1;
					} else if ("-".equals(str)) {
						ret = i2 - i1;
					} else if ("*".equals(str)) {
						ret = i2 * i1;
					} else if ("/".equals(str)) {
						ret = i2 / i1;
					}
					stack.push(ret);
				}
			} else {
				stack.push(Integer.parseInt(str));
			}
		}
		return stack.pop();
	}
    
    /**
     * 921. 使括号有效的最少添加
     * 
     * 给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
     * 
     * 从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
     * 
     * 它是一个空字符串，或者
     * 它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
     * 它可以被写作 (A)，其中 A 是有效字符串。
     * 给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入："())"
     * 输出：1
     * 示例 2：
     * 
     * 输入："((("
     * 输出：3
     * 示例 3：
     * 
     * 输入："()"
     * 输出：0
     * 示例 4：
     * 
     * 输入："()))(("
     * 输出：4
     * @param S
     * @return
     */
    public int minAddToMakeValid(String S) {
		if (S == null || S.length() == 0) {
			return 0;
		}
		int cnt = 0;
		Stack<Character> stack = new Stack<Character>();
		char[] chs = S.toCharArray();
		for (char ch : chs) {
			if (ch == '(') {
				stack.push(ch);
			} else {
				if (stack.isEmpty()) {
					cnt++;
				} else {
					stack.pop();
				}
			}
		}
		return cnt + stack.size();
    }
    
    /**
     * 946. 验证栈序列
     * 
     * 给定 pushed 和 popped 两个序列，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
     * 输出：true
     * 解释：我们可以按以下顺序执行：
     * push(1), push(2), push(3), push(4), pop() -> 4,
     * push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
     * 示例 2：
     * 
     * 输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
     * 输出：false
     * 解释：1 不能在 2 之前弹出。
     *  
     * 
     * 提示：
     * 
     * 0 <= pushed.length == popped.length <= 1000
     * 0 <= pushed[i], popped[i] < 1000
     * pushed 是 popped 的排列。
     * @param pushed
     * @param popped
     * @return
     */
    public boolean validateStackSequences(int[] pushed, int[] popped) {
		int len = pushed.length;
		int popIdx = 0;
		int pushIdx = 0;
		Stack<Integer> stack = new Stack<Integer>();
		while (popIdx < len && pushIdx <= len) {
			int cur = popped[popIdx];
			if (!stack.isEmpty() && stack.peek() == cur) {
				stack.pop();
				popIdx++;
			} else {
				while (pushIdx < len && cur != pushed[pushIdx]) {
					stack.push(pushed[pushIdx]);
					pushIdx++;
				}
				if (pushIdx < len && cur == pushed[pushIdx]) {
					pushIdx++;
					popIdx++;
				}else {
					return false;
				}
			}
		}
		return popIdx == len;
    }
    
    /**
     * 856. 括号的分数
     * 
     * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
     * 
     * () 得 1 分。
     * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
     * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
     *  
     * 
     * 示例 1：
     * 
     * 输入： "()"
     * 输出： 1
     * 示例 2：
     * 
     * 输入： "(())"
     * 输出： 2
     * 示例 3：
     * 
     * 输入： "()()"
     * 输出： 2
     * 示例 4：
     * 
     * 输入： "(()(()))"
     * 输出： 6
     *  
     * 
     * 提示：
     * 
     * S 是平衡括号字符串，且只含有 ( 和 ) 。
     * 2 <= S.length <= 50
     * @param S
     * @return
     */
	public int scoreOfParentheses(String S) {
		if (S == null || S.length() == 0) {
			return 0;
		}
		Stack<String> stack = new Stack<String>();
		char[] chs = S.toCharArray();
		for (char ch : chs) {
			if ('(' == ch) {
				stack.push("(");
			} else if (')' == ch) {
				String str = stack.pop();
				if ("(".equals(str)) {
					stack.push("1");
				} else {
					int tmp = Integer.parseInt(str);
					while (!stack.isEmpty() && !"(".equals(str = stack.pop())) {
						tmp += Integer.parseInt(str);
					}
					if ("(".equals(str)) {
						tmp *= 2;
					}
					stack.push("" + tmp);
				}
			}
		}
		if (stack.size() > 1) {
			String str = stack.pop();
			int tmp = Integer.parseInt(str);
			while (!stack.isEmpty()) {
				str = stack.pop();
				tmp += Integer.parseInt(str);
			}
			stack.push("" + tmp);
		}
		return Integer.parseInt(stack.pop());
	}
}
